package com.zyk.leetcode;

/**
 *
 * https://leetcode-cn.com/problems/map-sum-pairs/
 *
 * @author zhangsan
 * @date 2021/3/24 10:18
 */
public class C677 {

    public static class MapSum {
        public Node root;
        public MapSum() {
            root = new Node();
        }

        public void insert(String key, int val) {
            if(key == null) {
                return;
            }
            char[] chars = key.toCharArray();
            Node node = root;
            int path = -1;
            for (int i = 0; i < chars.length; i++) {
                path = chars[i] - 'a';
                node.pass++;
                node.sum += val;
                if(node.nodes[path] == null) {
                    node.nodes[path] = new Node();
                }
                node = node.nodes[path];
            }
            node.pass++;
            node.end++;
            if(node.end > 1) {
                int oldV = node.value;
                node = root;
                path = -1;
                for (int i = 0; i < chars.length; i++) {
                    path = chars[i] - 'a';
                    node.pass--;
                    node.sum -= oldV;
                    if(node.nodes[path] == null) {
                        node.nodes[path] = new Node();
                    }
                    node = node.nodes[path];
                }
                node.pass--;
                node.end--;
                node.sum -= oldV;
            }
            node.value = val;
            node.sum += val;
        }

        public int sum(String prefix) {
            if(prefix == null) {
                return 0;
            }
            char[] chars = prefix.toCharArray();
            int path = -1;
            Node node = root;
            for (int i = 0; i < chars.length; i++) {
                path = chars[i] - 'a';
                node = node.nodes[path];
                if(node == null) {
                    return 0;
                }
            }
            return node.sum;
        }

        public static class Node {
            public int pass;
            public int end;
            public int sum;
            public int value;
            public Node[] nodes;

            public Node() {
                nodes = new Node[26];
            }
        }

    }

    // for test
    public static void main(String[] args) {
        MapSum mapSum = new MapSum();
        mapSum.insert("apple", 3);
        System.out.println(mapSum.sum("ap"));
        mapSum.insert("app", 2);
        mapSum.insert("apple", 2);
        System.out.println(mapSum.sum("ap"));
    }

}
